home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / vol_400 / 412_01 / include / nodes.h < prev    next >
Encoding:
C/C++ Source or Header  |  1994-01-01  |  6.5 KB  |  210 lines
  1. #ifndef _nodes_H_
  2. #define _nodes_H_
  3.  
  4. #include <stdio.h>
  5. #include <stdlib.h>
  6. #include "object.h"
  7.  
  8. /*                        NODE_
  9.  
  10.     The base class NODE_ is derived from class SVOBJECT_ (sortable object)
  11.     and defines basic states that will be generated during the search process.
  12.     In other words, it defines the (abstract, since we're dealing with a base
  13.     class) objects that the search space consists of. Every class that is
  14.     derived from NODE_ must have the following functions:
  15.  
  16.     do_operator(): generates and returns one successor, i.e., a new state,
  17.                    when operator n is applied. Returns NULL when operator n 
  18.                    cannot be applied.
  19.     or expand():   returns a linked list of successors (the linked list must 
  20.                    be built by using the NODE_ *next field). This function
  21.                    is an alternative for do_operator(), either one has to be
  22.                    implemented! 
  23.     equal():       determines if 2 objects are the same, must return 1 if
  24.                    true and 0 if false.
  25.     display():     displays the object.
  26.  
  27.     Note that the virtual function eval() that is used to determine the order
  28.     of objects is not actually used in class NODE_, therefore it just
  29.     returns 1 (it can't be pure virtual because is it called in solve()).
  30.     For a real usage of this function see class BEST_NODE_ and UNI_NODE_.
  31.  
  32. */
  33.  
  34. class NODE_ : public SVOBJECT_
  35. {
  36.     public:
  37.         NODE_();
  38.  
  39.         virtual NODE_ *do_operator(int) const;
  40.     virtual NODE_ *expand(int) const;
  41.          // both of these not pure virtual since either may be implemented 
  42.     virtual int equal(const VOBJECT_ &) const = 0;
  43.         virtual int eval(const SVOBJECT_ &) const;
  44.              // not pure virtual since it's only needed in shortest path search
  45.     virtual void display() const = 0;
  46.  
  47.     NODE_ *getnext() const;
  48.     void setnext(NODE_ *);
  49.         void setparent(NODE_ *);
  50.         NODE_ *getparent() const;
  51.     private:
  52.         NODE_ *parent,     // to trace the solution path
  53.               *next;
  54. };
  55.  
  56.  
  57.  
  58. /*                        UNI_NODE_
  59.  
  60.     The base class UNI_NODE_ is derived from class NODE_ and defines
  61.     a special kind of NODE_'s: nodes that will be generated during the
  62.     search process of a uniform cost search. These nodes will be placed in
  63.     an ordered list, the order of 2 nodes is determined by eval() based
  64.     on their 'g-values'.
  65.  
  66.     G is a cost associated with the node: it's a measure of the cost
  67.     of getting from the start node to the current node. This value is computed
  68.     by compute_g().
  69.  
  70. */
  71.  
  72. class UNI_NODE_ : public NODE_
  73. {
  74.     public:
  75.         UNI_NODE_();
  76.         int eval(const SVOBJECT_ &) const;
  77.         int get_g() const;
  78.         void set_g(int);
  79.     private:
  80.         int g;        // cost of getting from the start node to this node
  81. };
  82.  
  83.  
  84.  
  85. /*                       BEST_NODE_
  86.  
  87.     The base class BEST_NODE_ is derived from class UNI_NODE_ which in
  88.     turn is derived from class NODE_. Class BEST_NODE_  defines
  89.     a special kind of NODE_'s: nodes that will be generated during the
  90.     search process of a best first search. These nodes will be placed in
  91.     an ordered list, the order of 2 nodes is determined by eval() based
  92.     on their 'f-values'.
  93.  
  94.     G (see unode.h) and F are costs associated with the node. G is a
  95.     measure of the cost of getting from the start node to the current node
  96.     and F the sum of G and H, the estimated cost of getting from the current
  97.     node to the goal node. These values are computed by compute_g() and
  98.     compute_h() respectively.
  99.  
  100. */
  101.  
  102. class BEST_NODE_ : public UNI_NODE_
  103. {
  104.     public:
  105.         BEST_NODE_();
  106.         int eval(const SVOBJECT_ &) const;
  107.         int get_f() const;
  108.         void set_f(int);
  109.     private:
  110.         int
  111.             f;          // f is g + h
  112. };
  113.  
  114.  
  115.  
  116. /*                       AONODE_
  117.  
  118.     Class AONODE_ defines nodes that will be generated in an AND-OR search
  119.     process. It is derived from class NODE_. AONODE_ is a base class for
  120.     class ORNODE_ and ANDNODE_ and should never be used for direct derivation.
  121.  
  122. */
  123.  
  124. #define OR 0
  125. #define AND 1
  126. #define UNSOLVABLE 0
  127. #define SOLVED 1
  128. #define DUNNO -1
  129.  
  130. class AONODE_ : public NODE_
  131. {
  132.     public:
  133.     AONODE_();
  134.     AONODE_(int);
  135.     AONODE_(int, int);
  136.  
  137.         void settype(int);
  138.         void setsolved(int);
  139.         int getsolved() const;
  140.         int gettype() const;
  141.         int getn_left() const;
  142.     void incn_left();
  143.         void decn_left();
  144.     private:
  145.         int type,        // is this an AND node or OR node?
  146.             solved,      // is the node labeled SOLVED, UNSOLVED or DUNNO?
  147.             n_left;      // number of successors left to be solved (AND node),
  148.                          // or: number of successors that may be still be
  149.                          // solved (OR node)
  150. };
  151.  
  152.  
  153. /*                     ANDNODE_
  154.  
  155.     Class ANDNODE_ is derived from class AONODE_. It must be used in a 
  156.     AND-OR search when a set of sub-problems, i.e, a set of new nodes,
  157.     is generated that ALL have to be solved. In this case the user should
  158.     create an ANDNODE_, by new ANDNODE_(), and pass every node representing
  159.     a sub-problem to this ANDNODE_: ANDNODE_::addsucc(some_ornode)).
  160.     Alternatively, an ANDNODE_ may be created by calling the second
  161.     constructor: new ANDNODE_(no_of_nodes) and then the successor nodes
  162.     may be passed by calling ANDNODE_::setsucc(n, node_n).
  163.  
  164. */
  165.  
  166. class ANDNODE_ : public AONODE_
  167. {
  168.     public:
  169.     ANDNODE_();
  170.     ANDNODE_(int no_nodes);
  171.     ~ANDNODE_();
  172.  
  173.     void setsucc(int, AONODE_ *);    // set successor n in succlist to...
  174.     void addsucc(AONODE_ *);         // add a successor to succlist
  175.         int getn_nodes() const;
  176.     AONODE_ *getsucc(int) const;     // get successor n from succlist
  177.  
  178.     void display() const;
  179.         int equal(const VOBJECT_ &) const;
  180.     private:
  181.     int n_nodes;                     // number of nodes in succlist
  182.     AONODE_ **succlist;         // this node's successors
  183. };
  184.  
  185.  
  186.  
  187. /*                        ORNODE_
  188.  
  189.     Class ORNODE_ is derived from class AONODE_, which in turn is derived
  190.     from class NODE_. It is used in the process of an AND-OR search and
  191.     should be used in conjunction with class AOSEARCH_. Nodes that are meant
  192.     to be generated in an AND-OR search should be derived from class ORNODE_.
  193.  
  194. */
  195.  
  196.  
  197. class ORNODE_ : public AONODE_
  198. {
  199.     public:
  200.     ORNODE_();
  201.  
  202.     void setsucc(AONODE_ *);
  203.     AONODE_ *getsucc() const;
  204.     private:
  205.     AONODE_ *succ;            // this node's successor
  206. };
  207.  
  208. #endif
  209.  
  210.